Proximal operator

In mathematical optimization, the proximal operator is an operator associated with a proper, lower semi-continuous convex function [math]\displaystyle{ f }[/math] from a Hilbert space [math]\displaystyle{ \mathcal{X} }[/math] to [math]\displaystyle{ [-\infty,+\infty] }[/math], and is defined by:

[math]\displaystyle{ \operatorname{prox}_f(v) = \arg \min_{x\in\mathcal{X}} \left(f(x) + \frac 1 2 \|x - v\|_\mathcal{X}^2\right). }[/math]

For any function in this class, the minimizer of the right-hand side above is unique, hence making the proximal operator well-defined. The proximal operator is used in proximal gradient methods, which is frequently used in optimization algorithms associated with non-differentiable optimization problems such as total variation denoising.

Properties

The [math]\displaystyle{ \text{prox} }[/math] of a proper, lower semi-continuous convex function [math]\displaystyle{ f }[/math] enjoys several useful properties for optimization.

• Fixed points of [math]\displaystyle{ \text{prox}_f }[/math] are minimizers of [math]\displaystyle{ f }[/math]: [math]\displaystyle{ \{x\in \mathcal{X}\ |\ \text{prox}_fx = x\} = \arg \min f }[/math].
• Global convergence to a minimizer is defined as follows: If [math]\displaystyle{ \arg \min f \neq \varnothing }[/math], then for any initial point [math]\displaystyle{ x_0 \in \mathcal{X} }[/math], the recursion [math]\displaystyle{ (\forall n \in \mathbb{N})\quad x_{n+1} = \text{prox}_f x_n }[/math] yields convergence [math]\displaystyle{ x_n \to x \in \arg \min f }[/math] as [math]\displaystyle{ n \to +\infty }[/math]. This convergence may be weak if [math]\displaystyle{ \mathcal{X} }[/math] is infinite dimensional.
• The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where [math]\displaystyle{ f }[/math] is the 0-[math]\displaystyle{ \infty }[/math] indicator function [math]\displaystyle{ \iota_C }[/math] of a nonempty, closed, convex set [math]\displaystyle{ C }[/math] we have that

[math]\displaystyle{ \begin{align} \operatorname{prox}_{\iota_C}(x) &= \operatorname{argmin}\limits_y \begin{cases} \frac{1}{2} \left\| x-y \right\|_2^2 & \text{if } y \in C \\ + \infty & \text{if } y \notin C \end{cases} \\ &=\operatorname{argmin}\limits_{y \in C} \frac{1}{2} \left\| x-y \right\|_2^2 \end{align} }[/math]

showing that the proximity operator is indeed a generalisation of the projection operator.

• A function is firmly non-expansive if [math]\displaystyle{ (\forall (x,y) \in \mathcal{X}^2) \quad \|\text{prox}_fx - \text{prox}_fy\|^2 \leq \langle x-y\ |\ \text{prox}_fx - \text{prox}_fy\rangle }[/math].
• The proximal operator of a function is related to the gradient of the Moreau envelope [math]\displaystyle{ M_{\lambda f} }[/math] of a function [math]\displaystyle{ \lambda f }[/math] by the following identity: [math]\displaystyle{ \nabla M_{\lambda f}(x) = \frac{1}{\lambda} (x - \mathrm{prox}_{\lambda f}(x)) }[/math].

• The proximity operator of [math]\displaystyle{ f }[/math] is characterized by inclusion [math]\displaystyle{ p=\operatorname{prox}_f(x) \Leftrightarrow x-p \in \partial f(p) }[/math], where [math]\displaystyle{ \partial f }[/math] is the subdifferential of [math]\displaystyle{ f }[/math], given by

[math]\displaystyle{ \partial f(x) = \{ u \in \mathbb{R}^N \mid \forall y \in \mathbb{R}^N, (y-x)^\mathrm{T}u+f(x) \leq f(y)\} }[/math] In particular, If [math]\displaystyle{ f }[/math] is differentiable then the above equation reduces to [math]\displaystyle{ p=\operatorname{prox}_f(x) \Leftrightarrow x-p = \nabla f(p) }[/math].

See also

• Proximal gradient method

External links

• The Proximity Operator repository: a collection of proximity operators implemented in Matlab and Python.
• ProximalOperators.jl: a Julia package implementing proximal operators.
• ODL: a Python library for inverse problems that utilizes proximal operators.